/*
 * Problem: 区间内素数的个数
 * Author: Yuanshun L
 * Created: 30-Nov-2021
 * Topic: 区间筛法
 */
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn = 1000000+10;
const int maxm = 1000000+5;


bool is_prime[maxn];
bool is_prime_small[maxm];

int solve(int a,int b){
    for(int i=0;i*i<b;i++){
        is_prime_small[i] = true;
    }
    for(int i=0;i<=b-a;i++){
        is_prime[i] = true;
    }

    for(ll i=2; i*i<b; i++){
        if(is_prime_small[i]){
            for(ll j = 2*i; j*j < b; j+=i){
                is_prime_small[j] = false;
            }
            for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i){
                is_prime[j-a] = false;
            }
        }
    }

    ll sum=0;
    for(int i=0;i<b-a;i++){
        if(is_prime[i]) sum++;
    }
    return sum;
}

int main(){
    ll a=4,b=15;
    cout<<"The number of prime in ["<<a<<","<<b<<"): "<< solve(a,b)<<endl;

    return 0;
}
